/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 晓星航
 * Date: 2023-12-05
 * Time: 8:44
 */
public class MatrixChainMultiplication {
    public static int matrixChainOrder(int[] dimensions) {
        int n = dimensions.length;
        int[][] dp = new int[n][n];

        // 对角线上初始化为0，表示单个矩阵相乘的代价为0
        for (int i = 1; i < n; i++) {
            dp[i][i] = 0;
        }

        // l为矩阵链长度
        for (int l = 2; l < n; l++) {
            for (int i = 1; i < n - l + 1; i++) {
                int j = i + l - 1;
                dp[i][j] = Integer.MAX_VALUE;

                // 遍历分割点k，求解最小代价
                for (int k = i; k <= j - 1; k++) {
                    int cost = dp[i][k] + dp[k + 1][j] + dimensions[i - 1] * dimensions[k] * dimensions[j];
                    if (cost < dp[i][j]) {
                        dp[i][j] = cost;
                    }
                }
            }
        }

        return dp[1][n - 1];
    }

    public static void main(String[] args) {
        int[] dimensions = {10, 20, 30, 40, 30};
        int minCost = matrixChainOrder(dimensions);
        System.out.println("Minimum cost of matrix multiplication: " + minCost);
    }
}
